package com.example.leetcode.DFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 * 示例 2：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *  
 *
 * 提示：
 *
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Description TODO
 * @date 2021/6/11 14:20
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_9_47 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2};

        List<List<Integer>> lists = permuteUnique(nums);
    }
    //方法一：回溯法 + stream
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        dfs(result, temp, nums,visited);

        result = result.stream().distinct().collect(Collectors.toList());

        return result;
    }
    private static void dfs(List<List<Integer>> result, List<Integer> temp, int[] nums, boolean[] visited) {
        if (temp.size() == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]){
                continue;
            }
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }


            visited[i] = true;
            temp.add(nums[i]);
            dfs(result,temp,nums,visited);
            // 回溯
            visited[i] = false;
            temp.remove(temp.size() - 1);
        }
    }
    // 方法二:回溯法 + 剪枝  77也是剪枝
    public static List<List<Integer>> permuteUnique1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        // 排序
        Arrays.sort(nums);
        dfs1(result, temp, nums,visited);
        return result;
    }
    private static void dfs1(List<List<Integer>> result, List<Integer> temp, int[] nums, boolean[] visited) {
        if (temp.size() == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 因为之前nums已经排过序了
            // i > 0 && nums[i] == nums[i - 1] && !visited[i - 1] 就能够避免出现重复的组合
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            temp.add(nums[i]);
            dfs1(result,temp,nums,visited);
            // 回溯
            visited[i] = false;
            temp.remove(temp.size() - 1);
        }
    }

}
